/*
 * @lc app=leetcode.cn id=6 lang=cpp
 *
 * [6] Z 字形变换
 */

// @lc code=start
class Solution
{
public:
  string convert(string s, int numRows)
  {
    int n = s.size(), max_interval = 2 * (numRows - 1);
    if (numRows == 1)
      return s;
    int step[] = {max_interval - 2, 2};
    string ans(n, '\0');
    // 填充第一行
    int idx = 0;
    for (int i = 0; i < n; i += max_interval)
      ans[idx++] = s[i];
    // 填充第二行~第n-1行
    for (int i = 1; i < numRows - 1; ++i) {
      for (int j = i, k = 0; j < n; ++k) {
        ans[idx++] = s[j];
        j += step[k % 2];
      }
      step[0] -= 2;
      step[1] += 2;
    }
    // 填充最后一行
    for (int i = numRows - 1; i < n; i += max_interval)
      ans[idx++] = s[i];
    return ans;
  }
};
// @lc code=end
